#ifndef UNIFIEDGRAPHTESTTEMPLATE_H_
#define UNIFIEDGRAPHTESTTEMPLATE_H_

#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/attributes/FlowEdgeAttributes.h"

#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/impls/wrap_igraph/WrapIGraph.h"

#include "graph_support/alg/shortest_path/Dejkstra.h"
#include "graph_support/alg/flow/Dinic.h"

#include "graph_support/utils/CollectionsInit.h"
#include "graph_support/utils/test_my_graph/CompareGraph.h"
#include "graph_support/utils/test_my_graph/MultipleCapacity.h"
#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/HashSupport.h"
#include "graph_support/utils/GraphTemplateUtils.h"


namespace GRAPH_SUPPORT_NS
{
namespace utils
{
namespace test_my_graph
{

/**
 * the easiest read-only test for graph
 * returns count of found edges
 */
template< typename GraphT >
int testEasyGraphAccess( GraphT & gr )
{
	return checkGraphSuperstructure( gr, gr );
}

/**
 * easy test for modifiable graph
 */
template< typename GraphT >
void testEasyCreateModifyCheckStructure( const std::vector< typename GraphT::GrVertex > & vertices )
{
	TEST_CASE_REQUIRES( vertices.size() > 2,
			"not enough vertices: " +
			boost::lexical_cast< std::string >( vertices.size() ) );

	typedef typename GraphT::GrEdge GrEdge;
	typedef typename GRAPH_SUPPORT_NS::impls::vector::VectorGraphTmpl< > StructProtGr;

	GraphT gr0( vertices.begin(), vertices.end() );

	std::vector< int > intRange( vertices.size() );
	for ( int i = 0; i < vertices.size(); i++ ) intRange[i] = i;
	StructProtGr spgr0( intRange );

	BOOST_CHECK( ! utils::findEdge( gr0, vertices[0], vertices[1] ) );
	gr0.addEdge( vertices[0], vertices[1] );
	spgr0.addEdge( 0, 1 );
	BOOST_CHECK( utils::findEdge( gr0, vertices[0], vertices[1] ) );
	BOOST_CHECK( ! utils::findEdge( gr0, vertices[1], vertices[0] ) );

	BOOST_CHECK( ! utils::findEdge( gr0, vertices[1], vertices[2] ) );
	BOOST_CHECK( ! utils::findEdge( gr0, vertices[2], vertices[1] ) );

	GraphT gr1( vertices.begin(), vertices.end(), true );
	StructProtGr spgr1( intRange, true );
	gr1.addEdge( vertices[1], vertices[2] );
	spgr1.addEdge( 1, 2 );
	BOOST_CHECK( utils::findEdge( gr1, vertices[1], vertices[2] ) );
	BOOST_CHECK( utils::findEdge( gr1, vertices[2], vertices[1] ) );

	gr1.addEdge( vertices[0], vertices[2] );
	spgr1.addEdge( 0, 2 );

	BOOST_CHECK_EQUAL( 1, checkGraphSuperstructure( gr0, spgr0 ) );
	BOOST_CHECK_EQUAL( 4, checkGraphSuperstructure( gr1, spgr1 ) );
}

/**
 * tests ability to store some edges
 * test case supposes that gr is "prepared" graph and already has some edges
 * returns count of found edges
 */
template < typename GraphT >
int testCollectEdges( GraphT & gr )
{
	std::vector< std::pair< typename GraphT::GrVertex, typename GraphT::GrVertex > > edgeDirectionClones;
	typedef typename GraphT::GrVertex GrVertex;
	typedef typename GraphT::VertexIterator VertexIterator;
	typedef typename GraphT::GrEdge GrEdge;
	typedef typename GraphT::EdgeIterator EdgeIterator;
	typedef typename GraphT::GrEdgePtr GrEdgePtr;
	std::vector< GrEdgePtr > edgePtrs;

	for ( VertexIterator vit = gr.getVerticesBeg(); vit != gr.getVerticesEnd(); ++vit )
	{
		GrVertex vertex = * vit;

		for ( EdgeIterator eit = gr.getEdgsBeg( vertex ); eit != gr.getEdgsEnd( vertex ); ++eit )
		{
			GrEdgePtr edgePtr = * eit;
			edgeDirectionClones.push_back(
					std::pair< GrVertex, GrVertex >( edgePtr->beg(), edgePtr->end() ) );
			edgePtrs.push_back( edgePtr );
		}
	}

	int n = edgeDirectionClones.size();
	for ( int i = 0; i < n; i++ )
	{
		BOOST_CHECK_EQUAL( edgePtrs[i]->beg(), edgeDirectionClones[i].first );
		BOOST_CHECK_EQUAL( edgePtrs[i]->end(), edgeDirectionClones[i].second );
	}

	return edgePtrs.size();
}

/**
 * wraps previous test case:
 * 		prepares graph and calls wrapped test.
 */
template < typename GraphT >
void testCollectEdges( const std::vector< typename GraphT::GrVertex > & verts )
{
	GraphT gr( verts );
	gr.addEdge( verts[0], verts[1] );
	gr.addEdge( verts[1], verts[2] );
	gr.addEdge( verts[2], verts[3] );
	gr.addEdge( verts[3], verts[0] );
	gr.addEdge( verts[0], verts[2] );
	BOOST_CHECK_EQUAL( 5, testCollectEdges( gr ) );
}

/**
 * dejkstra test for read-only graph
 *
 * checks if dejkstra finds at least shortest paths which were defined in dejkstraExpectedResult
 * dejkstraExpectedResult is supposed to have only edges like: src -> <some vertex>
 * so dejkstraExpectedResult is single-source shortest-path-closer of gr
 */
template< typename GraphT, typename DejkstraResultT >
void testDejkstra(
		GraphT & gr,
		const typename GraphT::GrVertex & src,
		DejkstraResultT & dejkstraExpectedResult )
{
	using namespace GRAPH_SUPPORT_NS::alg::shortest_path;
	using namespace GRAPH_SUPPORT_NS::impls::vector;
	using namespace GRAPH_SUPPORT_NS::impls;

	typedef typename GraphT::GrVertex GrVertex;
	typedef typename DejkstraResultT::GrEdgePtr DRGrEdgePtr;

	TEST_CASE_REQUIRES( gr.getVertexCount() == dejkstraExpectedResult.getVertexCount(),
			"invalid sizes" );

	std::vector< GrVertex > vertices( gr.getVertexCount() );
	std::copy( gr.getVerticesBeg(), gr.getVerticesEnd(), vertices.begin() );

	Dejkstra< GraphT > dejkstra( gr );
	dejkstra( src );

	int n = dejkstraExpectedResult.getVertexCount();
	for ( int i = 0; i < n; i++ )
	{
		if ( gr.num2vert( i ) == src )
		{
			continue;
		}
		boost::optional< DRGrEdgePtr > dresultEdge = utils::findEdge( dejkstraExpectedResult, gr.vert2num( src ), i );
		if ( dresultEdge )
		{
			BOOST_CHECK_EQUAL(
				dresultEdge.get()->getAttributes().getLength(),
				dejkstra.getDistance( vertices[i] ) );
		}
	}
}

/**
 * dejkstra test for modifiable graph
 * wraps previous test:
 * 		prepares graph and calls wrapped test
 */
template< typename GraphT >
void testDejkstra( const std::vector< typename GraphT::GrVertex > & vertices )
{
	using namespace GRAPH_SUPPORT_NS::attributes;
	using namespace GRAPH_SUPPORT_NS::alg::shortest_path;
	using namespace GRAPH_SUPPORT_NS::impls;
	using namespace GRAPH_SUPPORT_NS::impls::vector;

	typedef GraphT Graph;
	typedef typename Graph::GrVertex GrVertex;
	// TODO: typedef graph - name convention
	typedef VectorGraphTmpl< int, LengthEdgeAttributesTmpl< int > > ClGraph;

	TEST_CASE_REQUIRES( vertices.size() > 3, "not enough vertices" );

	GrVertex src = vertices[0];
	GraphT gr( vertices );
	gr.addEdge( src, vertices[1] );
	gr.addEdge( vertices[1], vertices[2] );
	gr.addEdge( vertices[2], vertices[3] );
	gr.addEdge( src, vertices[3] );

	Dejkstra< GraphT > dejkstra( gr );
	dejkstra( src );
	BOOST_CHECK_EQUAL( 1, dejkstra.getDistance( vertices[1] ) );
	BOOST_CHECK_EQUAL( 2, dejkstra.getDistance( vertices[2] ) );
	BOOST_CHECK_EQUAL( 1, dejkstra.getDistance( vertices[3] ) );

	// duplicates previous 3 checks
	ClGraph dejClGraph( vertices );
	dejClGraph.addEdge( 0, 1, ( LengthEdgeAttributesTmpl< int > ) 1 );
	dejClGraph.addEdge( 0, 2, ( LengthEdgeAttributesTmpl< int > ) 2 );
	dejClGraph.addEdge( 0, 3, ( LengthEdgeAttributesTmpl< int > ) 1 );
	testDejkstra( gr, vertices[0], dejClGraph );
}

/**
 * dinic test for read-only graph (modifies flow, doesn't modify graph structure)
 *
 * runs dinic and checks total flow
 */
template< typename GraphT >
void testDinic(
		GraphT & gr,
		const typename GraphT::GrVertex & src,
		const typename GraphT::GrVertex & dest,
		const typename GraphT::EdgeAttributes::Capacity & expectedCapacity)
{
	using namespace GRAPH_SUPPORT_NS::alg::flow;

	typedef typename GraphT::GrVertex GrVertex;
	typedef typename GraphT::EdgeAttributes EdgeAttributes;
	typedef typename EdgeAttributes::Capacity Capacity;

	Dinic< GraphT > dinic( gr );
	BOOST_CHECK_EQUAL( ( Capacity ) 0, dinic.getTotalFlow() );
	dinic( src, dest );

	BOOST_CHECK_EQUAL( expectedCapacity, dinic.getTotalFlow() );
}

/**
 * dinic test for modifiable graph
 * wraps previous test
 */
template< typename GraphT >
void testDinic( const std::vector< typename GraphT::GrVertex > & vertices )
{
	using namespace GRAPH_SUPPORT_NS::alg::flow;

	typedef typename GraphT::GrVertex GrVertex;
	typedef typename GraphT::EdgeAttributes EdgeAttributes;
	typedef typename EdgeAttributes::Capacity Capacity;

	TEST_CASE_REQUIRES( vertices.size() > 3, "not enough vertices" );

	GrVertex src = vertices[0];
	GrVertex dest = vertices[1];
	GraphT gr( vertices, true );
	gr.addEdge( src, dest, ( EdgeAttributes ) ( Capacity ) 123 );

	{
	Dinic< GraphT > dinic( gr );
	dinic( src, dest );
	BOOST_CHECK_EQUAL( ( Capacity ) 123, dinic.getTotalFlow() );
	}

	gr.addEdge( src, vertices[2], ( EdgeAttributes ) ( Capacity ) 45 );
	gr.addEdge( vertices[2], dest, ( EdgeAttributes ) ( Capacity ) 67 );

	{
	Dinic< GraphT > dinic( gr );
	dinic( src, dest );
	BOOST_CHECK_EQUAL( ( Capacity ) 168, dinic.getTotalFlow() );
	BOOST_CHECK_EQUAL( ( Capacity ) 45, dinic.getFlow( src, vertices[2] ) );
	BOOST_CHECK_EQUAL( ( Capacity ) -45, dinic.getFlow( vertices[2], src ) );
	}

	testDinic( gr, src, dest, ( Capacity ) 168 );
}

/**
 * dinic sophisticated test for modifiable graph
 *
 * requires GraphT::EdgeAttributes to be MultipleCapacity< ? >
 */
template< typename GraphT, int Cnt >
void testDinicOnMulticap( const std::vector< typename GraphT::GrVertex > & vertices )
{
	using namespace GRAPH_SUPPORT_NS::alg::flow;

	typedef typename GraphT::GrVertex GrVertex;
	typedef typename GraphT::EdgeAttributes EdgeAttributes;
	typedef typename EdgeAttributes::Capacity Capacity;

	TEST_CASE_REQUIRES( vertices.size() > 3, "not enough vertices" );

	int capacityStorage[] = { 123, 234, 345, 456, 567, 678, 789, 890, 901,
			112, 131, 415, 161, 718, 192 };
	int strgsz = sizeof( capacityStorage ) / sizeof( int );
	BOOST_CHECKPOINT( boost::lexical_cast< std::string >( strgsz ) +
			" - size of capacityStorage" );
	std::vector< Capacity > capacities;
	int edgesCount = 3;
	int * capStrgPtr = capacityStorage;
	int * capStrgLim = capStrgPtr + strgsz;
	for ( int i = 0; i < edgesCount; i++ )
	{
		TEST_CASE_REQUIRES( capStrgPtr != capStrgLim,
				"not enough capacity src int-s" );
		std::vector< int > tmp( Cnt );
		std::copy( capStrgPtr, capStrgPtr + Cnt, tmp.begin() );
		capacities.push_back( Capacity( tmp ) );
		capStrgPtr++;
	}
	BOOST_CHECKPOINT( boost::lexical_cast< std::string >( strgsz ) +
			" - capacities init completed" );
	int capacityPos = 0;

	GrVertex src = vertices[0];
	GrVertex dest = vertices[1];
	GraphT gr( vertices, true );
	gr.addEdge( src, dest, capacities[capacityPos++] );

	{
	Dinic< GraphT > dinic( gr );
	dinic( src, dest );
	BOOST_CHECK_EQUAL( capacities[0], dinic.getTotalFlow() );
	}

	gr.addEdge( src, vertices[2], capacities[capacityPos++] );
	gr.addEdge( vertices[2], dest, capacities[capacityPos++] );

	{
	Dinic< GraphT > dinic( gr );
	dinic( src, dest );
	BOOST_CHECK_EQUAL( capacities[0] + capacities[1], dinic.getTotalFlow() );
	BOOST_CHECK_EQUAL( capacities[1], dinic.getFlow( src, vertices[2] ) );
	BOOST_CHECK_EQUAL( ( ( Capacity ) 0 ) - capacities[1],
			dinic.getFlow( vertices[2], src ) );
	}

	testDinic( gr, src, dest, capacities[0] + capacities[1] );
}

template< typename GraphT >
void testIGraph( const std::vector< typename GraphT::GrVertex > & vertices )
{
	using namespace GRAPH_SUPPORT_NS;
	using namespace GRAPH_SUPPORT_NS::impls::wrap_igraph;
	using namespace GRAPH_SUPPORT_NS::alg::shortest_path;

	typedef typename GraphT::GrVertex GrVertex;
	typedef typename GraphT::EdgeAttributes EdgeAttributes;
	// TODO: graph name convention
	typedef WrapIGraph< EdgeAttributes > WGraph;
	typedef typename IGraph::EdgeAttributesImpl< EdgeAttributes >::CpAttributes IEdgeAttributesImpl;

	TEST_CASE_REQUIRES( vertices.size() > 3, "not enough vertices" );

	GraphT gr( vertices );
	IGraph * igr = dynamic_cast< IGraph * >( & gr );
	TEST_CASE_REQUIRES( igr != NULL, "graph is not implementation of IGraph" );
	WGraph wgr( * igr );

	gr.addEdge( vertices[0], vertices[1], 123 );
	gr.addEdge( vertices[0], vertices[2], 12 );
	{
	Dejkstra< WGraph > dejkstra( wgr );
	dejkstra( vertices[0] );
	BOOST_CHECK_CLOSE( 123.0, ( double ) dejkstra.getDistance( 1 ), 1e-5 );
	}
	igr->iaddEdge( 2, 1, IGraph::IEdgeAttributesPtr( new IEdgeAttributesImpl( EdgeAttributes( 23 ) ) ) );
	{
	Dejkstra< WGraph > dejkstra( wgr );
	dejkstra( vertices[0] );
	BOOST_CHECK_CLOSE( 35.0, ( double ) dejkstra.getDistance( 1 ), 1e-5 );
	}

	{
	std::stringstream buf;
	std::vector< size_t > dests;
	for ( IGraph::IEdgeIteratorPtr eit = igr->igetOutEdgesIterator( 0 ); eit->notFinished(); eit->next() )
	{
		dests.push_back( eit->getDestination() );
	}
	std::sort( dests.begin(), dests.end() );
	for ( std::vector< size_t >::iterator it = dests.begin(); it != dests.end(); ++it )
	{
		buf << * it << ", ";
	}
	// TODO: all BOOST_CHECK_EQUAL( std::string( " ...
	BOOST_CHECK_EQUAL( std::string( "1, 2, " ), buf.str() );
	}

	{
	std::stringstream buf;
	IGraph::IEdgeIteratorPtr eitptr = igr->igetOutEdgesIterator( 1 );
	IGraph::IEdgeIterator & eit = * eitptr;
	std::vector< size_t > dests;
	for ( igr->igetOutEdgesIterator( 0, eit ); eit.notFinished(); eit.next() )
	{
		dests.push_back( eit.getDestination() );
	}
	std::sort( dests.begin(), dests.end() );
	for ( std::vector< size_t >::iterator it = dests.begin(); it != dests.end(); ++it )
	{
		buf << * it << ", ";
	}
	BOOST_CHECK_EQUAL( "1, 2, ", buf.str() );
	}
}

}
}
}


/**
 * Facade of unified test system
 * tests whole functionality of template graph implementation:
 *
 * check access
 * check algorithms ( dejkstra, dinic )
 *
 * check modify
 *
 * check different node type
 * check different edge attributes
 *
 * and the most sophisticated: run dinic with complicated flow capacity
 */
#define RUN_UNIFIED_TEST_CASE_IGRAPH( GraphTmpl, TestAsIGraph )								\
	{																						\
	using namespace GRAPH_SUPPORT_NS::attributes;											\
	using namespace GRAPH_SUPPORT_NS::utils;												\
	using namespace GRAPH_SUPPORT_NS::utils::test_my_graph;									\
	using namespace GRAPH_SUPPORT_NS::impls;												\
	/**
	 * graph typedefs:
	 */																						\
	typedef GraphTmpl< int > IntGraph;														\
	typedef GraphTmpl< const char * > CharGraph;											\
	typedef GraphTmpl<																		\
		std::string,																		\
		Length1EdgeAttributes,																\
		Hash4StdString																		\
		> StrGraph;																			\
	typedef GraphTmpl<																		\
		int,																				\
		FlowEdgeAttributesTmpl< int >,														\
		stdext::hash< int >,																\
		stdext::equal_to< int >																\
		> IntFlowNet;																		\
	typedef GraphTmpl<																		\
		int,																				\
		FlowEdgeAttributesTmpl< MultipleCapacity< 5 > >,									\
		stdext::hash< int >,																\
		stdext::equal_to< int >																\
		> MultiFlowNet;																		\
	/**
	 * modify and access
	 * NOTE: if graph is read only - use read-only testDejkstra and
	 * testDinic to test access functionality
	 */																						\
	testEasyCreateModifyCheckStructure< IntGraph >(											\
			arr2vector< int >( ( const int [] ) { 0, 1, 2, 3 } ) );							\
	testEasyCreateModifyCheckStructure< IntGraph >(											\
			arr2vector< int >( ( const int [] ) { 10, 21, 32, 43, 54 } ) );					\
	testEasyCreateModifyCheckStructure< IntGraph >(											\
			arr2vector< int >( ( const int [] ) { -10, -21, -32, -43, -54 } ) );			\
	testEasyCreateModifyCheckStructure< CharGraph >(										\
			arr2vector< const char * >(														\
					( const char * const [] ) { "hello", "world", "blah-blah-blah" } ) );	\
	{ const std::string vs[] = {															\
			std::string( "hello"),															\
			std::string( "world" ),															\
			std::string( "blah-blah-blah" ) };												\
	testEasyCreateModifyCheckStructure< StrGraph >( arr2vector< std::string >( vs ) ); }	\
	/**
	 * test GrEdgeSynonym: tries to collect all edges
	 */																						\
	testCollectEdges< IntGraph >(															\
			arr2vector< int >( ( const int[] ) { 0, 1, 2, 3 } ) );							\
	/**
	 * algorithms: dejkstra
	 */																						\
	 testDejkstra< IntGraph >(																\
			 arr2vector< int >( ( const int[] ) { 0, 1, 2, 3 } ) );							\
	/**
	 * algorithms: dinic
	 */																						\
	 testDinic< IntFlowNet >(																\
			 arr2vector< int >( ( const int[] ) { 0, 1, 2, 3 } ) );							\
	/**
	 * algorithms: dinic with sophisticated capacity
	 */																						\
	 testDinic< MultiFlowNet >(																\
			 arr2vector< int >( ( const int[] ) { 0, 1, 2, 3 } ) );							\
	/**
	 * algorithms: dinic with VERY sophisticated capacity
	 */																						\
	testDinicOnMulticap< MultiFlowNet, 5 >(													\
			arr2vector< int >( ( const int[] ) { 0, 1, 2, 3 } ) );							\
	if ( TestAsIGraph )	\
	{	\
		testIGraph< GraphTmpl< int, LengthEdgeAttributesTmpl< int > > >(						\
				 arr2vector< int >( ( const int[] ) { 0, 1, 2, 3 } ) );	\
	}	\
	}

#define RUN_UNIFIED_TEST_CASE( GraphTmpl )													\
		RUN_UNIFIED_TEST_CASE_IGRAPH( GraphTmpl, true )

#endif /* UNIFIEDGRAPHTESTTEMPLATE_H_ */
